package com.bigshen.algorithm.iHash.solution01SubarraySumEqualsK;

import java.util.HashMap;
import java.util.Map;

/**
 * 560. Subarray Sum Equals K
 * Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.
 *
 * Example 1:
 * Input: nums = [1,1,1], k = 2
 * Output: 2
 *
 * Example 2:
 * Input: nums = [1,2,3],
 * Output: 2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    public int subarraySum(int[] nums, int k) {
        if(null == nums || nums.length == 0) {
            return 0;
        }
        //int[] sumArray = new int[nums.length];
        Map<Integer, Integer> map = new HashMap<>();
        int total = 0;
        int sum = 0;
        map.put(0, 1);
        for (int i = 0; i < nums.length; i ++) {
            sum += nums[i];
            if (map.containsKey(sum-k)) {
                total += map.get(sum-k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return total;
    }

    // hash解法 O(N)
    private int sumHash(int[] array, int k) {

        // 先将数组元素求和，组成求和的数组sums;
        int[] sums = new int[array.length];
        sums[0] = array[0];
        for (int i = 1; i < array.length; i ++) {
            sums[i] = sums[i-1] + array[i];
        }

        int total = 0;
        Map<Integer, Integer> map = new HashMap();
        map.put(0, 1); // 和减去k为0，表明和为需要的元素，此时map中value需要记录1次
        for (int i = 0; i < sums.length; i++) {

            // 如果当前sum与k的差在map中出现，表明相减可以得到k，有匹配值
            if (map.containsKey(sums[i]-k)) {
                total += map.get(sums[i]-k);
            }

            // 将求和的值作为key，和出现的次数作为value，存入map中
            if (map.containsKey(sums[i])) {
                map.put(sums[i], map.get(sums[i])+1);
            } else {
                map.put(sums[i], 1);
            }

        }
        return total;
    }

}
